Poisoned Wine
Here is another exciting puzzle posted on Facebook by Konstantin Knop.
Puzzle. Eight glasses of wine are placed in a circle on a round table. Three sages are invited to take the following challenge. In the presence of the first sage, five glasses are filled with good wine and the other three with poisoned wine, indistinguishable from the good wine. After drinking the poisoned wine, the person will die a terrible tormented death. Each sage has to drink one full glass. The first sage is not allowed to give any hints to the other sages, but they can see which glass he chooses before making their own selection. The three sages can agree on their strategy beforehand. What is the strategy to keep them all alive?
An extra question. Does a strategy exist if fewer than eight glasses are placed around the table?
Let’s start with two trivial variations. If there is only one sage, s/he knows which glass to drink. Now, suppose there is only one poisoned glass and any number of sages. If the total number of good glasses is not less than the number of sages, the solution is obvious. The first sage drinks the glass clockwise from the poisoned one, and the other sages continue clockwise.
The next slightly less trivial case involves two sages and two poisoned glasses. If the total number of glasses is at least five, the sages are safe. The reason: there are at least two good glasses in a row. So the sages can agree that the first one drinks a good glass followed clockwise by another good glass. If the total number of glasses is less than 5, there is no reliable strategy, as the reader can check.
The above idea works if the number of sages is S, the number of poisoned glasses is P, and the total number of glasses is T, where T is greater than SP. Then, the strategy is the same since there is a guaranteed continuous stretch of S good glasses.
On the other hand, one can argue that for S and P more than 1, and T = S + P, it is impossible to find a strategy.
Our original problem corresponds to the case S = P = 3, and T = 8. Presumably, the strategy doesn’t exist if S = P = 3, and T < 8. If the 8-glasses problem is difficult, here is a much easier version, corresponding to the case S = 2, P = 3, and T = 6.
Share:An Easier Puzzle. Six glasses of wine are placed in a circle on a round table. Two sages are invited to take the following challenge. In the presence of the first sage, three glasses are filled with good wine and the other three with poisoned wine, indistinguishable from the good wine. After drinking the poisoned wine, the person will die a terrible tormented death. Each sage has to drink one full glass. The first sage is not allowed to give any hints to the other sages, but they can see which glass he chooses before making their own selection. The two sages can agree on their strategy beforehand. What is the strategy to keep them all alive?
Chris Tunstall:
Divide the glasses into pairs of opposite glasses. At least one pair has two good glasses. If the pair of glasses half way between the good pair are also a good pair, then there exist four sequences of glasses GXGXG around the circle. If the pair of glasses half way between the first good pair are mixed, then there exists one sequence of glasses GXGXG around the circle. If the pair of glasses half way between the first good pair are both poisoned, then three of the remaining four glasses are good and there exists one sequence of glasses GXGXG around the circle. The strategy is that sage 1 chooses the first (most counterclockwise) G of any of the GXGXG sequences and the others proceed clockwise skipping a glass each time.
7 September 2022, 11:00 amL33tminion:
> The three sages can agree on their strategy beforehand.
I think you mean “two sages” for that last problem? As you mention, it isn’t solvable for three.
There are either three poisoned cups in a row (starting from the group of three, XXX___), two in a row (starting from the group of two (XX_X__ or (XX__X_), or no two adjacent (X_X_X_). That last case doesn’t have two adjacent safe glasses. But in any of those cases, there’s some safe glass where two glasses further clockwise is also safe.
7 September 2022, 11:44 amtanyakh:
Thanks, L33tminion. I fixed it.
7 September 2022, 11:49 amChris Tunstall:
For seven glasses of which three are poisoned a strategy involving always skipping glasses won’t work because the sages must step over at least two glasses, both of which might be good, leaving at least one sage with a poisoned glass. Hence the strategy must involve using two adjacent glasses and a third glass one step away. The version of that strategy (doing it clockwise) that works for GGGPGPP fails for GGGPPGP, hence there’s no safe strategy. For six glasses, no glasses can be skipped because a skipped glass might be good, leaving a sage with a poisoned glass. A strategy with no glasses skipped fails for anything other than GGGPPP, so again no safe strategy. For five or fewer glasses, someone’s going to die.
7 September 2022, 2:12 pmChris Tunstall:
In the seven glasses case, the first sage could always choose his glass with either his left hand or his right hand, signalling a clockwise or counterclockwise strategy. I think that could work, but it’s not strictly playing by the rules.
7 September 2022, 2:48 pmJonathan Kariv:
That was fun. I’m wondering if we can do any assymptotics for N is terms of S and P? My first thought here was “Hey N=2^S=2^P, maybe that’s the trick”. Looking at S=P=2 it wasn’t but I there might be some interesting generalisations?
8 September 2022, 4:18 amrosie:
This made me think “this problem’s underspecified” until I read part of your commentary. Does the first sage know which glasses contain poisoned wine? If so, Knop should have said so. He said “poisoned wine, indistinguishable from the good wine” thus indicating that nobody can distinguish it from the good wine.
11 September 2022, 3:45 pmPuzzled:
Another solution of 8 glasses puzzle. Consider two groups 1,3,5,7 and 2,4,6,8. One group contains at most one glass with poisoned wine. So the first sage can select a good glass N such that N+2 and N+4 are good too (if a number M exceeds 8 we take M-8).
12 September 2022, 4:26 amsed:
I find three strategies using that little program I wrote for the 8 glasses and 3 poisoned:
http://sedcore.eu.org/tmp/dig.c
I don’t know what to think. Did I solve it or not? Is it cheating? The computer explored the state space (which is small), then I just post-process what it says. What kind of thinking is this? I wrote the program, yes. But… I don’t know. I’m puzzled.
12 September 2022, 8:58 amCristóbal Camarero:
Kariv, we may get some infintely large families. We have the base case P=1 with S=T-1. Then, we may double it in the way Puzzled says. This is, from a (S,P,T) we get another (S’,P’,T’) with S’=S, P’=2P+1, T’=2T. Iterating k-1 times from a base solution we get for any S, P=2^k-1, T=2^(k-1)*(S+1).
The main presented puzzle can then be seen as the base S=2, P=1, T=3 doubled into S=2, P=2+1=3, T=3*2=6. The easier puzzle as the base S=3, P=1, T=4 doubled into S=3, P=3, T=8.
A good question is whether there is any solvable instance harder than the these sequences.
14 September 2022, 3:50 amTanya Khovanova's Math Blog » Blog Archive » Poisoned Wine - New Marathi Live:
[…] Source link […]
16 September 2022, 3:32 amSanjay Godse:
Easy method for 8 glasses problem.
Five different arrangements are possible for 8 glasses.
16 September 2022, 12:33 pmYou can always find in each arrangement 3 alternate safe glasses. A will select the middle one and B and C will select the other two.
Sanjay Godse:
In my previous comment, A, B and C are the three prisoners, First, Second and Third respectively.
16 September 2022, 12:36 pmLeo:
The first sage can always find an unpoisoned glass such that the glass 2 to the left of it and 2 to the right of it are unpoisoned, too.
I tried to see this as follows: If we number our glasses 0_7, then either for the four even or for the gour odd ones, there is only one poisoned one. Assume that among {0,2,4,6} only one is poisoned.
Then the other three can be drunk and the sage can pick the central one of then. (We have to think mod 8 since they are arranged circularly)
E.g if 2 is poisoned then the sage drinks from 6.
I don’t know how to solve the extra question without direct verificstion case by case though…
18 September 2022, 7:18 amTanya Khovanova's Math Blog » Blog Archive » Rulers to the Rescue:
[…] recently posted a cute puzzle about poisoned wine. Today, I would like to discuss this puzzle’s variation with N total glasses, of which two […]
25 November 2022, 1:43 pm